/**
 * 剑指 Offer 54. 二叉搜索树的第k大节点
 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
 */
const { createTreeNode } = require('../../libs/public');

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
function kthLargest(root, k) {
  const stack = [];
  let node = root;
  let count = k;
  while (node) {
    while (node) {
      stack.push(node);
      node = node.right;
    }
    do {
      node = stack.pop();
      if (count <= 1) {
        return node.val;
      }
      count -= 1;
      if (node.left) {
        node = node.left;
        break;
      } else {
        node = null;
      }
    } while (stack.length);
  }
  return 0;
}

console.log(kthLargest(createTreeNode([3, 1, 4, null, 2]), 1) === 4);
console.log(kthLargest(createTreeNode([5, 3, 6, 2, 4, null, null, 1]), 3) === 4);
